import pulp

def find_all_subsets_with_minimized_deviation(arr, target_sum):
    # 创建问题实例
    prob = pulp.LpProblem("Subset Sum Problem with Minimized Deviation", pulp.LpMinimize)

    # 创建二进制决策变量，表示每个元素是否被选择
    n = len(arr)
    x = pulp.LpVariable.dicts("x", range(n), cat='Binary')

    # 创建偏差变量
    sum_deviations = pulp.LpVariable("sum_deviations", lowBound=0)

    # 实际总和
    group_sum = pulp.lpSum([arr[i] * x[i] for i in range(n)])

    # 添加约束条件：实际总和与目标总和的差距不超过偏差变量
    prob += group_sum - target_sum <= sum_deviations
    prob += target_sum - group_sum <= sum_deviations
    prob += sum_deviations <= 10
    # 设置目标函数：最小化偏差
    prob += sum_deviations

    subsets = []
    solver = pulp.PULP_CBC_CMD(msg=1,timeLimit=5)
    used_indices = set()
    for i in range(10):
        for j in used_indices:
            prob += x[j] == 0
        # 求解当前问题
        prob.solve(solver)

        if pulp.LpStatus[prob.status] != 'Optimal':
            break

        # 提取结果
        current_solution = [pulp.value(x[xi]) for xi in x]
        subset = [arr[i] for i in range(n) if pulp.value(x[i]) > 0.5]
        actual_sum = sum(subset)
        deviation = abs(actual_sum - target_sum)
        subsets.append((subset, actual_sum, deviation))
        for i, val in enumerate(current_solution):
            if val > 0.5:
                used_indices.add(i)



    return subsets

# 输入数组和目标总和
arr = [12.87, 12.87, 12.87, 13.59, 17.01, 39.87, 43.74, 43.74, 44.46, 44.46, 47.07, 51.39, 51.39, 67.14, 111.87, 39.87,
       43.74, 43.74, 44.01, 44.46, 47.07, 50.4, 51.39, 67.14, 111.87, 114.39,200]
target_sum = 200

# 查找所有和尽可能接近200的子集
subsets = find_all_subsets_with_minimized_deviation(arr, target_sum)

# 打印结果
if subsets:
    print(f"找到以下和尽可能接近 {target_sum} 的子集:")
    for idx, (subset, actual_sum, deviation) in enumerate(subsets, start=1):
        print(f"子集 {idx}: {subset}, 和: {actual_sum}, 偏差: {deviation}")
else:
    print(f"未找到任何子集。")